package jm.data.structure.tree;

import java.util.Comparator;

/**
 * @Description 平衡二叉搜索树
 * @date 2022/4/20 15:15
 */
public class BBST<E> extends BinarySearchTree<E> {

    public BBST(){
        this(null);
    }

    public BBST(Comparator<E> Comparator){
        super(Comparator);
    }

    /**
     * 左旋
     * @param grand
     */
    protected void rotateLeft(Node<E> grand){
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;
        afterRotate(grand, parent, child);
    }

    /**
     * 右旋
     * @param grand
     */
    protected void rotateRight(Node<E> grand){
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;
        afterRotate(grand, parent, child);
    }

    /**
     * 旋转之后 更新 parent 和 height
     * @param grand
     * @param parent
     * @param child
     */
    protected void afterRotate(Node<E> grand,Node<E> parent,Node<E> child){
        // 更新 parent

        // 更新 p 的 parent 使成为当前子树的根节点
        parent.parent = grand.parent;
        if (grand.isLeftChild()){
            grand.parent.left = parent;
        }else if (grand.isRightChild()){
            grand.parent.right = parent;
        }else { // grand 是根节点
            root = parent;
        }

        // 更新 p.left 的 parent
        if (child != null){
            child.parent = grand;
        }
        // 更新 g 的 parent
        grand.parent = parent;
    }

    /**
     * 旋转
     * @param r 子树根节点
     * @param a
     * @param b
     * @param c
     * @param d
     * @param e
     * @param f
     * @param g
     */
    protected void rotate(
            Node<E> r,
            Node<E> a, Node<E> b, Node<E> c,
            Node<E> d,
            Node<E> e, Node<E> f, Node<E> g){

        // 让 d 成为这颗子树的根节点
        d.parent = r.parent;
        if (r.isRightChild()){
            r.parent.right = d;
        }else if (r.isLeftChild()){
            r.parent.left = d;
        }else {
            root = d;
        }

        // a b c
        b.left = a;
        if (a != null){
            a.parent = b;
        }
        b.right = c;
        if (c != null){
            c.parent = b;
        }

        // e f g
        f.left = e;
        if (e != null){
            e.parent = f;
        }
        f.right = g;
        if (g != null){
            g.parent = f;
        }

        // b d f
        d.left = b;
        b.parent = d;
        d.right = f;
        f.parent = d;
    }
}
